/**
 * 
 */
package com.gwcloud.leetcode.hot100;

/**
 * @ClassName   : Leetcode0494 
 * @author      : ganwei 
 * @date        : 2020年5月23日
 * @Description : Leetcode0494
 */
public class Leetcode0494 {
	int result = 0;
	/**
	 * -回溯算法
	 */
    public int findTargetSumWays(int[] nums, int S) {
    	backtrace(nums, 0, S);
    	return result;
    }
    public void backtrace(int[] nums, int start, int target){
    	if(start == nums.length){
    		if( target == 0){
    			result += 1;
    		}
    		return;
    	}

    	
    	backtrace(nums, start+1, target+nums[start]);
    	backtrace(nums, start+1, target-nums[start]);
    }
    /**
     * -主函数
     */
    public static void main(String[] args){
    	Leetcode0494 l0494 = new Leetcode0494();
    	int[] nums = {1, 1, 1, 1, 1};
    	System.out.println(l0494.findTargetSumWays(nums, 3));
    }
}
